import java.util.Arrays;

public class Solution1510 {
    public boolean winnerSquareGame(int n) {
        int[] f=new int[n+1];
        Arrays.fill(f,-1);
        f[0]=0;
        return dfs(f,n)==1;
    }

    private int dfs(int[] f, int n) {
        if (f[n]==-1){
            int t=-1;
            for (int i=1;i*i<=n;i++){
                if (dfs(f,n-i*i)==0){
                    t=1;
                    break;
                }
            }
            if (t==1){
                f[n]=1;
            }else {
                f[n]=0;
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1510().winnerSquareGame(17));
    }
}
